package com.zlk.algorithm.algorithm.dynamicPlan.arraySum;

import org.junit.Test;

// 数组中不能选相邻元素的最大累加和
// 给定一个数组，可以随意选择数字
// 但是不能选择相邻的数字，返回能得到的最大累加和
// 测试链接 : https://leetcode.cn/problems/house-robber/
public class Code02_HouseRobber {
    @Test
    public void test(){
        int[] nums = new int[]{2,7,9,3,1};
        System.out.println(rob(nums));
    }

    /**
     * 以i位置结尾的最大累加和
     * dp[i]  Max(dp[i-2],dp[i-3])
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        if(nums.length==1){
            return nums[0];
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int cur = nums[i];
            int p1=0;
            int p2=0;
            if(i-2>=0){
                p1=dp[i-2];
            }
            if(i-3>=0){
                p2=dp[i-3];
            }
            dp[i]=cur+Math.max(p1,p2);
        }
        return Math.max(dp[nums.length-1],dp[nums.length-2]);
    }


    /**
     * dp【i】0到i最大累加和
     *  要i  Math.max(nums[i]+dp[i-2],nums[i])    (考虑dp[i-2]可能负数)
     *  不要i dp[i-1]
     * @param nums
     * @return
     */
    public int rob3(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[1],nums[0]);
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i-1],Math.max(nums[i]+dp[i-2],nums[i]));
        }
        return dp[nums.length-1];
    }


    /**
     * 空间压缩
     * @param nums
     * @return
     */
    public int rob2(int[] nums) {
        if(nums.length==1){
            return nums[0];
        }
        int pre = nums[0];
        int prePre = 0;
        int pppre = 0;
        for (int i = 1; i < nums.length; i++) {
            int tempPre = pre;
            int tempprePre = prePre;
            int cur = nums[i];
            int p1=0;
            int p2=0;
            if(i-2>=0){
                p1=prePre;
            }
            if(i-3>=0){
                p2=pppre;
            }
            pre=cur+Math.max(p1,p2);
            prePre = tempPre;
            pppre = tempprePre;
        }
        return Math.max(pre,prePre);
    }
}
